A semiconductor integrated circuit (IC) has a large number of electronic components, such as transistors, logic gates, diodes, wires, etc., that are fabricated by forming layers of different materials and of different geometric shapes or polygons on various regions of a silicon wafer. The design of an integrated circuit transforms a circuit description into a geometric description called a layout. The process of converting specifications of an integrated circuit into a layout is called the physical design.
Geometric information about the placement of the nodes and components onto the chip is determined by a placement process and a routing process. The placement process is a process for placing electronic components or circuit blocks on the chip and the routing process is the process for creating interconnections between the blocks and components according to the specified netlist. Since modern IC designs often contain an extremely large number of such components, electronic design automation (“EDA”) tools and software are normally used by designers to facilitate and perform the place and route process.
A layout may contain a number of different types and configurations of shapes, e.g., polygonal shapes such as triangles, rectangles, etc. In one approach for implementing EDA tools, a separate data structure may be employed to store and maintain each different type of polygon in the layout. For instance, for each triangular-shaped polygon in the layout, a triangle-based data structure may be used to track those objects. For each rectangular-shaped polygon, a rectangle-based data structure may be used to track these objects. The advantage of this approach is that the dedicated data structure for each polygon type can be optimized for the exact set of information required to track its associated objects.
However, drawbacks also exist for this approach. A significant drawback is that the proliferation of different data structures also requires a corresponding increase in the complexity and size of the EDA tool that operates upon the data structures. The EDA tool normally includes a set of functions or operations that operate upon the polygons in the layout. Each operation supported by the EDA tool should support the different shapes and combinations of shapes in the layout. If there are a number of different data structures corresponding to the different available shapes, then the EDA tool must be configured to operate upon those different data structures. This increases the complexity and cost of creating and maintaining the EDA tool.